package com.zac.coroutine.algorithm.leetcode.array

/**
 * author zac
 * date 2025/8/5
 *
 * 283. 移动零
 * 简单
 * 相关标签
 * premium lock icon
 * 相关企业
 * 提示
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 *
 * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * 示例 2:
 *
 * 输入: nums = [0]
 * 输出: [0]
 *
 */
object MoveZeroes {

    @JvmStatic
    fun main(args: Array<String>) {
        val nums = intArrayOf(4, 2, 4, 0, 0, 3, 0, 5, 1, 0)
        moveZeroes4(nums)
        for (i in nums) {
            print("$i ,")
        }
    }

    fun moveZeroes(nums: IntArray): Unit {
        var start: Int
        var nextStart = 0
        var haveMiddleZero = true
        var remember: Boolean
        var moveTimes = 0
        while (haveMiddleZero) {
            haveMiddleZero = false
            remember = false
            start = nextStart
            val end = nums.size - moveTimes
            for (i in start until end) {
                if (i < end - 1 && nums[i] == 0) {
                    if (nums[i + 1] == 0) {
                        haveMiddleZero = true
                        if (!remember) {
                            nextStart = i
                            remember = true
                        }
                    }
                    nums[i] = nums[i + 1]
                    nums[i + 1] = 0
                }
            }
            moveTimes++
            if ((nums.size - moveTimes) <= start + 1) break
        }
    }

    // 1 0 1 0 1 0 1
    // 1 1 0 0 1 0 1
    // 1 1 1 0 0 0 1
    // 1 1 1 1 0 0 0
    fun moveZeroes1(nums: IntArray): Unit {
        for (i in 0 until nums.size) {
            if (nums[i] == 0) {
                var haveNotZeroNum = false
                for (j in i + 1 until nums.size) {
                    if (nums[j] != 0) {
                        haveNotZeroNum = true
                        nums[i] = nums[j]
                        nums[j] = 0
                        break
                    }
                }
                if (!haveNotZeroNum) break
            }
        }
    }

    /**
     * 我自己看着题解写的双指针
     * 方法一：双指针
     * 思路及解法
     *
     * 使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
     * 右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
     * 注意到以下性质：
     * 左指针左边均为非零数；
     * 右指针左边直到左指针处均为零。
     * 因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。
     */
    fun moveZeroes2(nums: IntArray): Unit {
        var leftP = 0
        var rightP = 1

        // 对比官方题解写法:这里其实只需要判断右侧指针是否到达终点既可
        while (/*前半部分不必要*/leftP < nums.size - 1 && rightP < nums.size) {
            // 对比官方题解:这里其实不需要判断左边指针指向是否为0,因为,如果前面的值为0,那么两个指针都在同时往前移动
            // swap等同于无效
            // 当遇到左指针为0 此时右指针也为0,然而此时只有右指针在移动,并且移动到非0时
            // 才会进行交换
            // 此时若左指针指向的下一个值不为0,则不进行交换且双指针继续往下执行
            // 当左指针再次遇到0,则右指针指向下一个不为0时再进行交换
            // 好复杂. 自己都要绕晕了
            /*这个判断不必要*/if (nums[leftP] == 0) {
                if (nums[rightP] != 0) {
                    nums[leftP] = nums[rightP]
                    nums[rightP] = 0
                    leftP++
                }
            } else {
                leftP++
            }
            rightP++
        }
    }

    // 官方题解双指针,比我的要简洁
    fun moveZeroes3(nums: IntArray) {
        val n = nums.size
        var left = 0
        var right = 0
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right)
                left++
            }
            right++
        }
    }

    fun swap(nums: IntArray, left: Int, right: Int) {
        val temp = nums[left]
        nums[left] = nums[right]
        nums[right] = temp
    }

    /**
     * 大牛题解
     * 使用一个指针n往后移动,记录为0的坐标.
     * i往后移.当nums[ i ]非0,将其与n替换位置,n往后移
     * i到达终点后n即为最后一个0的后一位
     * 最后从这一位开始全部补0
     */
    fun moveZeroes4(nums: IntArray) {
        var n = 0
        for (i in 0 until nums.size) {
            if (nums[i] != 0) {
                nums[n] = nums[i]
                n++
            }
        }
        for (i in n until nums.size) {
            nums[i] = 0
        }
    }

}
















